#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

struct ListNode
{
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution
{
public:
    ListNode *ReverseList(ListNode *head)
    {
        // 迭代的方式
        if (head == nullptr || head->next == nullptr)
            return head;

        // 到这里保证不越界访问
        // 三指针
        ListNode *prev = head;
        ListNode *mid = prev->next;
        ListNode *cur = mid->next;

        while (cur)
        {
            // 反转
            mid->next = prev;
            prev = mid;
            mid = cur;
            cur = cur->next;
        }

        // 细节处理
        mid->next = prev;
        head->next = nullptr;

        return mid;
    }

    //链表合并：非递归
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        if(list1 == nullptr) return list2;
        if(list2 == nullptr) return list1;

        ListNode* newhead = nullptr;
        ListNode* tail = newhead;

        while(list1 && list2)
        {
            if(nullptr == newhead)
            {
                if(list1->val < list2->val)
                {
                    newhead = tail = list1;
                    list1 = list1->next;
                }
                else
                {
                   newhead = tail = list2;
                   list2 = list2->next; 
                }
            }
            else
            {
                //开始合并
                if(list1->val < list2->val)
                {
                    tail->next = list1;
                    tail = list1;
                    list1 = list1->next;
                }
                else
                {
                    tail->next = list2;
                    tail = list2;
                    list2 = list2->next;
                }
            }
        }
        
        if(list1) tail->next = list1;
        if(list2) tail->next = list2;
            
        return newhead;
    }

    //链表合并：非递归
    ListNode* mergeTwoLists1(ListNode* list1, ListNode* list2) 
    {
        if(list1 == nullptr) return list2;
        if(list2 == nullptr) return list1;

        //到这里链表不为空
        if(list1->val < list2->val)
        {
            //前者小于后者，将后者继续递归
            list1->next = mergeTwoLists1(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists1(list1, list2->next);
            return list2;
        }
    
    //判断二叉树的子结构
    //判断两个树是否相等
    bool isSubtree(TreeNode* A, TreeNode* B)
    {
        if(B == nullptr) return true; //比较的树判断完

        if(A == nullptr) return false; //两棵树不相等，tree2还有节点没有判断完

        if(A->val != B->val) return false;

        return isSubtree(A->left, B->left) && isSubtree(A->right, B->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) 
    {
        if(A == nullptr || B == nullptr) return false;

        bool ret = false;
        //从根节点开始判断
        if(A->val == B->val)
        {
            ret = isSubtree(A, B);
        }
        //判断左子树
        if(ret != true)
        {
            ret = isSubStructure(A->left, B);
        }
        //判断右子树
        if(ret != true)
        {
            ret = isSubStructure(A->right, B);
        }
        return ret;
    }

    //二叉树的镜像
    TreeNode* Mirror(TreeNode* root) 
    {
        if(root == nullptr) return nullptr;

        //记录左右子树交换后的变化
        TreeNode* left = Mirror(root->left);
        TreeNode* right = Mirror(root->right);

        //不采用前序遍历，前序只造成局部节点交换

        //后续遍历，交换左右节点指向
        root->left = right;
        root->right = left;

        return root;//返回交换后的根节点
    }

    //删除链表重复节点
    ListNode* deleteDuplicates(ListNode* head) 
    {
        if(head == nullptr || head->next == nullptr) return head;

        //利用双指针
        ListNode* prev = head;  
        ListNode* cur = prev;

        while(cur)
        {
            if(prev->val != cur->val)
            {
                prev->next = cur;
                prev = cur;
            }
            cur = cur->next;
        }
        //cur遍历到结尾，可能prev后面节点还有重复数据，直接链空去重
        prev->next = nullptr;

        return head;
    }
};

#include <stack>
//找出栈中最小值
class MinStack {
private:
    stack<int> s;
    stack<int> smin;
public:
    MinStack() {
    }
    
    void push(int x) 
    {
        //辅助栈处理
        if(smin.size() == 0)
        {
            smin.push(x);
        }
        else
        {
            int top = smin.top();
            if(x > top) smin.push(top);
            else smin.push(x);
        }

        s.push(x);
    }
    
    void pop() {
        smin.pop();
        s.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return smin.top();
    }
};

int main()
{
    return 0;
}